链表——判断一个链表是否是回文结构

实现：利用栈先进后出的特点。设链表长为N

1. 若N为偶数，则将链表右边N/2部分的数据压入栈，
   全部出栈后判断它是否与原链表的左边N/2部分的数据相同。
2. 若N为奇数，则忽略中间的数，将右边(N-1)/2的内容压入栈，
   检查栈顶到栈底值是否与左边(N-1)/2部分的内容相同。
   （注意：题目中的是回文结构与有回文结构时不同的！）

注意与删除链表的中间节点的不同，删除链表的中间节点是为了获得左半边的最后一个数（123）45
而判断回文中，是为了获得右半边第一个数123（45）。

import java.util.Stack;
public class IsPalindrome {
	public static boolean isPalindrome(Node head) {
		if (head == null || head.next == null) {
			return true;
		}
		//获取右半边的第一个节点right
		Node cur = head;
		Node right = head.next;
		while (cur.next != null && cur.next.next != null) {
			//right每次走一步，current每次走两步
			right = right.next;
			cur = cur.next.next;
		}
		Stack<Node> stack = new Stack<>(); //注意栈中的类型为Node
		//将右半边的所有数压入stack
		while(right != null) {
			stack.push(right);
			right = right.next;
		}
		//逐个弹出栈中的数据，与原链表左边部分进行比较
		while(!stack.isEmpty()) {
			if (head.data != stack.pop().data) {
				return false;
			} //先执行上面的，如果不等，就返回false,下面也不会执行；
			//如果上面不成立，则不会返回false，继续执行下面的
			head = head.next; //这句话意思是，当前数字匹配成功，开始搜索下个节点
		}
		return true;
	}

	//Test
	public static void main(String[] args) {
		Node head = new Node(1); 
		Node node1 = new Node(2);
		Node node2 = new Node(3);
		Node node3 = new Node(2);
		Node node4 = new Node(2);
		head.next = node1;
		node1.next = node2;
		node2.next = node3;
		node3.next = node4;
		System.out.println(isPalindrome(head));
	}
}

判断一个字符串是否是回文结构
实现：

1. 先将字符串转成字符数组。
2. 两个指针start从头开始往后移，end从后往前移，只要start<end就循环。
3. 判断是否相等。
4. 一旦start>=end就退出循环(等号说明到了中间元素了，不需要比较）。

char[] cha = str.tocharArray();
int start = 0;
int end = cha.length - 1;
while(start < end) {
	if (cha[start] != cha[end]){
		return false;
	}
	end--;
	start++;
}
return true;